This invention relates to methods of transmitting data, cell-based methods of transmitting data, and to corresponding systems, apparatus and software for transmitting or receiving data.
Cell-based protocols for transmission systems are well known. Cells (also called packets or frames) are sent individually, and routed over a network using addressing information in the cell. Usually the data need to be fitted into a number of such cells. Some protocols specify variable length cells. Some are connection oriented such as S.N.A., A.T.M., X-25 and frame relay. Others are connectionless, for example IP. Such known protocols can be seen to have a layered structure with overhead for different functions being added at successively lower layers, at a transmitting end. At a receiving end, the overhead is successively stripped out once its function has been achieved. One type of overhead is error protection information. Generally, it has been considered worthwhile to include error detection bits at some layer, and a mechanism at a higher layer to request retransmission of some part of the data if the data are sensitive to errors.
Error correction codes such as Hamming codes are also known. These enable most but not all errors to be detected and corrected. Error correction codes are typically used in applications such as data storage on hard disks. When data are stored, error correction is generated and stored along with the data. On retrieval of data from the disk, the error correction information can be used to detect and correct errors.
Such techniques are not used in cell based protocols because the large overhead which would be required is considered to be prohibitive, particularly for larger cells, and because error correction codes are relatively poor at detecting some types of errors. Therefore, to ensure that the number of undetected errors is minimised, error detection codes such as Cyclic Redundancy Check (CRC) codes or Reed-Solomon codes are used, together with retransmission of cells or groups of cells. One such known protocol, the ATM protocol will now be discussed in more detail.
The ATM protocol is an example of a cell-based protocol designed for data transfer over high speed, low error rate digital networks for multiple service types. ATM Adaptation Layers (AALs) shape the service data for the ATM protocol and provide error protection characteristics dictated by the properties of the transmission medium and the service. The data units entering the AAL have to be protected to satisfy the ITU-T""s assured and unassured service recommendations. This error protection is achieved by concatenating each data unit with a header and trailer resulting in a variable length frame structure. The frame is then segmented into cells for transmission by the ATM protocol which in turn may have further protection.
The ATM protocol is characterised by the cells being of fixed length, and by its support for circuit emulation. ATM cells have headers with routing information and with header error correction information. There are currently a number of different AALs specified, each with different error handling features. For example AAL 5 includes error detection information, though not correction information at the frame level, but none is provided at the cell level, at least for the cell payload.
The ITU-T has recommended that erroneous frames be recovered by retransmissions of the entire frame in preference to individual cell retransmissions. Assured services carry significant disadvantages because of the retransmission system, including:
prolonged buffering at the transmitter, (i.e. at an access node where the ATM network is entered)
prolonged buffering at the receiver,
complex protocol acknowledgement structures and
increased latency from acknowledgement messages and data retransmission.
Protocols have been developed to provide selective cell retransmissions, for example BLINKBLT, although they cannot offer serious reductions in the service latency or buffering requirements. For these reasons the ITU-T is proposing to restrain assured services to point-to-point connections.
There is a selection of applications that requires low, though not perfect, error performance. The inventors have established that the overall error rate is limited by uncontrollable errors. Furthermore, any retransmissions penalise the application causing it to buffer data for prolonged periods. Many applications would benefit from bufferless transmission provided the error rates are sufficiently low, especially where equipment cost is an important factor.
GB 2216752 shows transmitting a block of data spread over a number of packets with additional redundant information for error correction being added to the block before transmission (forward error correction at the block level). The correction in the receiver can be carried out if sufficient correct packets are received. An automatic repeat request mechanism (ARQ) is used at the packet level if insufficient correct packets are received. In an alternative embodiment, the ARQ is carried out as soon as a packet is detected as being erroneous rather than waiting to see if sufficient packets from a block are received.
Various schemes including cell header correction without payload error correction are shown in EP 0516042, EP 0600380, EP 0445730, and U.S. Pat. No. 5383203. WO 95/14971 shows error detection based on redundant information spread over a number of frames or cells. Error detection triggers resynchronisation of transmitter and receiver encoding/ decoding methods.
The present invention aims to improve on the known methods.
According to one aspect of the invention, there is provided a method of transmitting data comprising the steps of:
supplementing the data with error detection information;
forming the supplemented data into at least one cell, the cell comprising cell routing information and a cell payload and wherein the cell payload comprises at least a portion of the supplemented data and error correction information for the portion; transmitting the cell to a destination;
correcting an error in the cell using said error correction information;
extracting the payload from the cell;
and detecting uncorrected errors in the data using said error detection information and reporting the uncorrected errors to an error processing means.
By performing error correction at lower level than the error detection, the amount of overhead required can be reduced, and/or a reduction in retransmissions can be achieved. This enables buffering at the access nodes to be reduced. In turn this can reduce the cost of access node hardware. The buffering hardware often makes up a significant proportion of the cost of an access node. The reduction in retransmission will also reduce congestion and delays in transmission.
Offering low-level error correction, possibly combined with higher-level error detection, allows frame-based transmission circuits requiring high integrity but tolerant of very rare discarded packets to operate without the need for buffering for retransmission at the transmitter. The control of such buffers is often difficult and costly in memory and processing power and its removal provides a useful advantage.
The main advantages are: 1. reduced retransmissions, or 2. reduced buffering and acceptance of the occasional loss. In the second case, the loss is much less than without this technique.
According to another aspect of the invention, there is provided a cell-based method of transmitting data comprising the steps of: dividing the data across two or more of :the cells; transmitting the cells to a destination; performing error detection and correction on the divided data in each cell individually; recombining the corrected divided data; and detecting uncorrected errors in the recombined data.
According to another aspect of the invention, there is provided a method of transmitting data comprising the steps of: forming the data into at least one frame, the frame also comprising error detection information relating to the data in that frame, sufficient to achieve an undetected bit error rate of substantially 10xe2x88x9221; forming each frame into at least one cell, the cell comprising cell routing information and a cell payload, the payload comprising at least a portion of the frame; transmitting the cell to a destination; extracting the frame from the cell; and detecting errors in the frame from the error detection information for that frame, and reporting them to an error processing means.
This enables the number of undetected errors in a frame to be negligible, without an unnecessary increase in the overhead at the cell or frame level.
Another aspect of the invention provides a system comprising means arranged to carry out such steps.
Other aspects of the invention provide apparatus for a transmitting side or a receiving side of the system, or software stored on a computer readable medium for carrying out the steps of: receiving data transmitted in a cell-based form, the data being divided across two or more of the cells; performing error detection and correction on the divided data in each cell individually; recombining the corrected divided data; and detecting uncorrected errors in the recombined data.
If the error detection information is added as part of a framing process, then errors can be detected on a frame by frame basis. Thus retransmission can be requested of only those frames with errors, if desired.
Advantageously the error correction information may comprise a Hamming code. This is a particularly efficient and easy to implement form of error correction code.
Advantageously the error detection information may comprise a CRC code. Again this code is particularly efficient and easy to implement.
Advantageously the cell transmission is by a connection oriented method. This implies an end to end connection is established before data is transmitted, and the connection is released after transmission. Advantages include the fact that sequence integrity is normally maintained, and that incremental processing to transfer data once the connection is established, is reduced.
Advantageously, before transmission, a desired bandwidth request, or tolerable maximum error rate request or other quality of service request for the transmission is sent to the link. This enables resources such as bandwidth, and error processing hardware to be allocated more efficiently.
Advantageously the error processing means is operable to request retransmission of some or all of the data if an uncorrected error is detected. Thus applications which are sensitive to data errors can be assured of any level of error rate, even down to 10xe2x88x9221 as desired.
Advantageously the cell transmission is carried out by an ATM protocol. This protocol can handle a wide range of types of data having different bandwidth, delay and error limitations. The short size of ATM cells (53 octets) means that error correction is relatively efficient, because the probability of uncorrectable two bit errors in a single cell reduces as the cell size is reduced.
Advantageously the frames are suitable for use with an ATM adaption layer. Such layers are suitable for adapting long variable length payloads into short fixed length ATM cells, or for adapting constant bit rate payloads into a sufficient rate of ATM cells. An intermediate step in these protocols involves forming variable length frames, to facilitate buffer allocation, multiplexing, timing, selective retransmission, and protection against cell loss.
Advantageously the CRC code is 37 or 38 bits long. This length enables the undetected error rate to reach substantially 10xe2x88x9221, which can be regarded as negligible. Clearly the code length can be varied somewhat without losing the advantage.
Advantageously the Hamming code is 9 bits long. This enables all one bit errors in a cell of up to 512 bits in length, to be corrected. An ATM cell is 384 bits in length, not including the header, which has its own error protection.
Advantageously a sequence number of 5 bits or more is included in each cell. This gives an appreciable decrease in the probability of an undetected error caused by loss of sequence owing to cell rerouting, over that achieved by a 4 bit sequence number, as is normally used in an ATM cell, created by AAL 3/4 for example.
Advantageous features may be combined together and with any of the aspects of the invention, as would be apparent to a skilled person.